/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

struct ListNode{
	int val;
	ListNode  *next;
	ListNode(int x):val(x),next(NULL){}
};

ListNode * buildListNode(int *num,int n){
	ListNode *head=NULL,*p,*q;
	for(int i=0;i<n;i++){
		q=new ListNode(num[i]);
		if(head){
			p->next=q;
		}else{
			head=q;
		}
		p=q;
	}
	return head;
}
void print(ListNode *p){
	while(p){
		cout<<p->val<<",";
		p=p->next;
	}
	cout<<endl;
}
ListNode* mergeKLists1(vector<ListNode*>& lists) {
	ListNode *head=NULL,*p,*q;
	
	//cout<<lists[0]->val<<endl;
	int *whiteList=(int *)malloc(sizeof(int)*lists.size());
	int length=lists.size();

	for(int i=0;i<length;i++){
		whiteList[i]=i;
	}
	
	while(length>0){
		int min=2147483647 ,index=-1;
		for(int i=0;i<length;){
			if(lists[whiteList[i]]!=NULL){
				if(lists[whiteList[i]]->val<min){
					min=lists[whiteList[i]]->val;
					index=whiteList[i];
				}
				i++;
			}else{
				for(int k=i+1;k<length;k++)
					whiteList[k-1]=whiteList[k];
				length--;
			}
		}
		if(min==2147483647)
			continue;
		q=new ListNode(min);
		if(head){
			p->next=q;
		}else{
			head=q;
		}
		p=q;
		lists[index]=lists[index]->next;
	}
	return head;
}
ListNode* mergeTwoList(ListNode* a,ListNode* b){
	ListNode head(0),*p=&head;
	while(a||b){
		if(a==NULL){
			p->next=b;
			p=b;
			b=b->next;
		}else if(b==NULL){
			p->next=a;
			p=a;
			a=a->next;
		}else{
			if(a->val>b->val){
				p->next=b;
				p=b;
				b=b->next;
			}else{
				p->next=a;
				p=a;
				a=a->next;
			}
		}
	}
	return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
	ListNode *head=NULL,*p,*q;
	vector<ListNode*>result=lists,temp;
	if(lists.size()<1){
		return NULL;
	}
	while(result.size()>1){
		temp.clear();
		for(int i=0;i+1<result.size();i+=2){
			temp.push_back(mergeTwoList(result[i],result[i+1]));
		}
		if(result.size()%2==1){
			temp.push_back(result[result.size()-1]);
		}
		result=temp;
	}
	return result[0];
}
int main(){
	int numbers[]={1,2,6,7};
	int numbers2[]={4,5,11};
	int numbers3[]={3,8,90};
	vector<ListNode*>lists;
	ListNode *l1,*l2,*l3,*head;
	l1=buildListNode(numbers,sizeof(numbers)/sizeof(int));
	lists.push_back(l1);
	l2=buildListNode(numbers2,sizeof(numbers2)/sizeof(int));
	lists.push_back(l2);
	l3=buildListNode(numbers3,sizeof(numbers3)/sizeof(int));
	lists.push_back(l3);

	head=mergeKLists(lists);
	print(head);

	system("pause");
	return 0;
}
*/